package Sort;

import java.util.Arrays;

public class RadixSort {

  public static void main(String[] args) {
    int[] num = new int[]{53,3,542,748,14,214};

    radixSort(num);

    System.out.println(Arrays.toString(num));
  }

  public static void radixSort(int[]num){

    //1.得到数组中最大的数的位数
    int max = num[0]; //假设第一数就是最大數
    for(int i = 1; i < num.length; i++) {
      if (num[i] > max) {
        max = num[i];
      }
    }
    //得到最大数是几位数
    int maxLength = (max + ""). length();

    //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    //说明
    //1.二维数组包含10个一维數组
    //2.为了防止在放入数的时候，数据溢出,则每个一维数组(桶),大小定为num.length
    //3.明确，基数排序是使用空间换时间的经典算法
    int[][] bucket = new int[10][num.length];

    //为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
    //可以这里理解
    //比如: bucketElementCounts[0]，记录的就是bucket[0] 桶的放入数据个数
    int[] bucketElementCounts = new int[10] ;

    for (int i = 0,n = 1; i < maxLength; i++,n = n*10) {

      for(int j = 0; j < num.length; j++) {
        //取出每个元素的个位的值
        int digitOfElement = num[j] /n % 10;
        //放入到对应的桶中
        bucket[digitOfElement] [bucketElementCounts[ digitOfElement]] = num[j];
        bucketElementCounts[digitOfElement ]++;
      }

      //按照这个桶的顺序(- -维数组的下标依次取出数据，放入原来数组)
      int index = 0;
      //遍历每一禰,并将桶中的数据，放入到原数组
      for(int k = 0; k < bucket.length; k++) {//共10个桶
        //如果桶中,有数据,我们才放入到原数组
        if(bucketElementCounts[k] != 0) {
          //循环该徜即第k个桶(即第k个- -维数组),放入
          for(int l = 0; l < bucketElementCounts[k]; l++) {
            //取出元素放入到arr
            num[index++] = bucket[k][l];
          }
        }
        //第l轮处理后,需要将每个bucketElementCounts[k] = 0! ! ! !
        bucketElementCounts[k] = 0;

      }
    }

  }
}
